import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int[][] array = new int[2][2];
        array[0][0] = 1;

    }
}
class Solution3 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int m = intervals.length;
        List<int[]> ans = new ArrayList<>();
        int[][] tmp = new int[m+1][2];
        int j = 0;
        for(int i=0; i<m; i++){
            tmp[i] = intervals[i];
        }
        tmp[m] = newInterval;
        if(m+1 < 2) return tmp;
        Arrays.sort(tmp,(a,b)->a[0]-b[0]);
        for(int i=1; i<m+1; i++){
            if(tmp[i-1][1]>=tmp[i][0]){
                tmp[i][0] = tmp[i-1][0];
                tmp[i][1] = Math.max(tmp[i-1][1],tmp[i][1]);
            }else{
                ans.add(tmp[i-1]);
            }
            if(i+1 == m+1)
                ans.add(tmp[i]);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
class Solution2 {
    /*
    1. 要找到最小的值，最好的方法就是把这堆石头分成总量相似的两队
    2. i: 前 i 个石头
       j: 能装 j 重量的石头
       dp[i][j]: 在能装 j 重量时，得到前 i 个石头中的最大价值
       dp[i][j] = max(dp[i-1][j],dp[i-1][j-stone[i]]+stone[i])
    3. 变成一维dp
    注：一维dp遍历时，j必须从后往前遍历(否则会出错，不知道画个图就懂了)
       j: 能装 j 重量的石头
       dp[j]: 在能装 j 重量时，得到前 i 个石头中的最大价值
       dp[j] = max(dp[j],dp[j-stone[i]]+stone[i])
    */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int x: stones){
            sum += x;
        }
        int[] dp = new int[sum/2+1];
        for(int j=stones[0]; j<sum/2+1; j++){
            dp[j] = stones[0];
        }
        for(int i=1; i<stones.length; i++){
            for(int j=sum/2; j>=stones[i]; j--){
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[sum/2];
    }
}
class Solution {
    /**
     正数和： left   负数和： -right
     得到：  left + right = sum(nums)
     left - right = target
     可以得出： left = (sum+target)/2
     j: 前i个数的结果为 j
     dp[j]: 不同表达式的数目
     dp[j] += dp[j-nums[i]]
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int x : nums){
            sum += x;
        }
        if(target < 0 && sum < -target) return 0;
        if((sum+target)%2 != 0) return 0;
        int left = (sum+target)/2;
        if(left < 0) left = -left;
        int[] dp = new int[left+1];
        dp[0] = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=left; j>=nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[left];
    }
}